class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0)=='0'){
            return 0;
        }
        int[] db = new int[s.length()];
        db[0] = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                if (s.charAt(i - 1) == '0') {
                    return 0;
                } else {
                    if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {
                        if (i - 2 < 0) {
                            db[i] = 1;
                        } else {
                            db[i] = db[i - 2];
                        }
                    }
                }
            } else {
                if (s.charAt(i - 1) == '0') {
                    db[i] = db[i - 1];
                } else {
                    if (Integer.parseInt(s.substring(i - 1, i + 1)) <= 26) {
                        if (i - 2 < 0) {
                            db[i] = 2;
                        } else {
                            db[i] = db[i - 1] + db[i - 2];
                        }
                    } else {
                        db[i] = db[i - 1];
                    }
                }

            }
        }
        return db[s.length() - 1];
    }
}